package zuoshen_video;
import java.util.*;


public class GraphProblems {
    
    //图的通用数据结构三件套

    //顶点类
     class Node<T> {
         T val; //节点含有的信息
         int in;//入度个数
         int out;//出度个数
         List<Node<T>> nexts; //出度节点
         List<Edge<T>> edges; //出渡边

         public Node(T val) {
             this.val = val;
             this.in = 0;
             this.out = 0;
             nexts = new ArrayList<>();
             edges = new ArrayList<>();
         }
     }

     //边类
     class Edge<T> {
        Node<T> in;//入度节点
        Node<T> out;//出度节点
        int weight;//边上的权重
        public Edge(Node<T> in, Node<T> out, int weight) {
            this.in = in;
            this.out = out;
            this.weight = weight;
        }
     }

     //图类
     class Graph<T> {
        //每个节点具有对应的编号，用于不同图的转换
        Map<Integer, Node<T>> nodes;
        Set<Edge<T>> edges;

        public Graph(){
            this.nodes = new HashMap<>();
            this.edges = new HashSet<>();
        }
     }

    //三元组：[val, from, to]表示from -> to, val指的是边上的权值
    public Graph<Integer> fromTritupleCreateGraph(int[][] tritp) {
        Graph<Integer> res = new Graph<>(); //生成空图
        int[] t;
        Node<Integer> from, to;
        Edge<Integer> e;
        for (int i = 0; i < tritp.length; i++) {
            t = tritp[i];
            if (!res.nodes.containsKey(t[1])) res.nodes.put(t[1], new Node<Integer>(t[1]));
            if (!res.nodes.containsKey(t[2])) res.nodes.put(t[2], new Node<Integer>(t[2]));
            from = res.nodes.get(t[1]);
            to = res.nodes.get(t[2]);
            from.nexts.add(to);
            e = new Edge<>(from, to, t[0]);
            from.edges.add(e);
            from.out++;
            to.in++;
            res.edges.add(e);
        }
        return res;
    }

    public void bfsGraph(Node<Integer> node) {
        if (node == null) return;
        Queue<Node<Integer>> queue =  new LinkedList<>();
        queue.offer(node);
        Node<Integer> cur = node;
        Set<Node<Integer>> set = new HashSet<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                System.out.println(cur.val);
                for (Node<Integer> next: cur.nexts) 
                    if (!set.contains(next)) {
                        set.add(next);
                        queue.offer(next);
                    }
            }
        }
    }

    public void dfsGraph(Node<Integer> node) {
        if (node == null) return;
        Node<Integer> cur = node;
        Set<Node<Integer>> set = new HashSet<>();
        Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
        stack.push(cur);
        System.out.println(cur); //总是在入栈时打印
        set.add(cur); //记录遍历过的节点
        while (!stack.isEmpty()) {
            cur = stack.pop();//当下面循环中的if条件一直不成立，stack会不断的pop，最终栈空；set.size() 也有参考效果吗？
            for (Node<Integer> next: cur.nexts) {
                if (!set.contains(next)) {
                    System.out.println(next.val);
                    set.add(next);
                    //将两个节点同时压栈
                    stack.push(cur);
                    stack.push(next);
                    break;//结束遍历nexts的行为
                }
            }
        }
    }

    public List<Node<Integer>> topoSort(Graph<Integer> graph) {
        Map<Node<Integer>, Integer> map = new HashMap<>();
        Queue<Node<Integer>> queue = new LinkedList<>();
        List<Node<Integer>> res = new ArrayList<>();
        for (Node<Integer> node: graph.nodes.values()) {
            int in = node.in;
            map.put(node, in);
            if (in == 0) queue.offer(node);
        }
        int size = graph.nodes.size(), num;
        Node<Integer> cur;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            res.add(cur);
            for (Node<Integer> node : cur.nexts) {
                map.put(node, (num = map.get(node) - 1));
                if (num == 0) queue.offer(node);
            }
        }
        if (res.size() < size) return null;//拓扑排序失败，存在环
        else return res; //成功，返回一个可能的排序结果
    }

    //kruscal算法最小生成树
    public List<Edge<Integer>> kruscalMST(Graph<Integer> graph) {
        //以小顶堆来排序边集合，排序规则为边的权值
        Queue<Edge<Integer>> queue = new PriorityQueue<>((e1, e2) -> e1.weight - e2.weight);
        queue.addAll(graph.edges);
        List<Edge<Integer>> res = new ArrayList<>();
        Edge<Integer> cur;
        Node<Integer> from, to;
        NodeUnionFindSet ufs = new NodeUnionFindSet(graph.nodes.values());
        while (!queue.isEmpty()) {
            cur = queue.poll();
            from = cur.in;
            to = cur.out;
            if (!ufs.isConnenct(from, to)) {
                //只有当前最短边的端点两端不再一个区域中，才会选择当前边，并将这两个集合合并
                ufs.union(from, to);
                res.add(cur);
            }
        }
        //如果利用res变成的set更新graph的edges集合，并再利用一次遍历修改边指针，就能得到最小生成树
        return res;
    }

    class NodeUnionFindSet {
        public Map<Node<Integer>, Node<Integer>> parent;
        public Map<Node<Integer>, Integer> weight;

        public NodeUnionFindSet(Collection<Node<Integer>> set) {
            parent = new HashMap<>();
            weight = new HashMap<>();
            for (Node<Integer> node: set) {
                parent.put(node, node);
                weight.put(node, 1);
            }
        }

        public Node<Integer> find(Node<Integer> node) {
            Node<Integer> p;
            if ((p = parent.get(node)) == node) return node;
            Node<Integer> root = find(p);
            parent.put(node, root);
            return root;
        }

        public int union(Node<Integer> node1, Node<Integer> node2) {
            Node<Integer> r1 = find(node1), r2 = find(node2);
            if (r1 == r2) return weight.get(r1);
            int w1 = weight.get(r1), w2 = weight.get(r2);
            if (w1 > w2) {
                weight.put(r1, w1 + w2);
                parent.put(r2, r1);
            } else {
                weight.put(r2, w1 + w2);
                parent.put(r1, r2);
            }
            return w1 + w2;
        }

        public boolean isConnenct(Node<Integer> node1, Node<Integer> node2) {
            return find(node1) == find(node2);
        }
    }


    //通过普利姆算法最小生成树
    /* 
        每到达一个新节点，就会将其周围所有没有**解锁**的边解锁
        选择最小的那个没遍历过的边加入结果
    */
    public List<Edge<Integer>> primMST(Graph graph) {
        List<Edge<Integer>> res = new ArrayList<>();
        Collection<Node<Integer>> nodes = graph.nodes.values();
        Set< Node<Integer>> nodeSet = new HashSet<>();//存储已经到达过的顶点
        Set<Edge<Integer>> edgeSet = new HashSet<>();//存储已经收进去的边
        //小顶堆存储所有边
        Queue<Edge<Integer>> queue = new PriorityQueue<>((e1, e2) -> e1.weight - e2.weight);
        Edge<Integer> cur;
        Node<Integer> to;
        for (Node<Integer> node : nodes) {
            for (Edge<Integer> e : node.edges) {
                if (!edgeSet.contains(e)) {
                    queue.offer(e);
                    edgeSet.add(e);
                }
            }
            while (!queue.isEmpty()) {
                    //得到一个最小边
                cur = queue.poll();
                to = cur.out; //这是可能的一个可以遍历边的顶点
                if (!nodeSet.contains(to)) {
                    //未被访问的节点
                    nodeSet.add(to);
                    res.add(cur); //此边的另一边节点未被访问，说明当前边的两边没有连通，可以加到结果集合中
                    for (Edge<Integer> e : to.edges) {
                        if (!edgeSet.contains(e))  {
                            edgeSet.add(e);
                            queue.offer(e);
                        }
                    }
                }
            }
            //此for循环一般只需要执行一次，不要也行,目的是为了出现了森林的情况
            break;
        }
        return res;
    }

    //通过Dijsktral算法生成最小路径
    //node：起点
    public Map<Node<Integer>, Integer> dijsktral(Node<Integer> node) {
        Map<Node<Integer>, Integer> res = new HashMap<>();
        Set<Node<Integer>> set = new HashSet<>();
        res.put(node, 0); //不存在的顶点视为无穷大，也可以显示指定无穷大，省得一次判断
        Node<Integer> cur;
        int curDistance = 0, temp;
        while((cur = miniumDistanceNode(res, set)) != null) {//还有没使用的顶点
            curDistance = res.get(cur); //不需要累加，而是一种只取，因为上一次计算覆盖时已经累加过了
            for (Edge<Integer> e: cur.edges) {
                if (!res.containsKey(e.out)) { //无穷大可以进行覆盖
                    res.put(e.out, curDistance + e.weight);
                } else if (res.get(cur) >  (temp = curDistance + e.weight)) { //当前获取的路径比之前更短，进行覆盖
                    res.put(e.out, temp);
                }
            }
            //将当前的节点标记为已访问，加入黑名单
            set.add(cur);
        }
        return res;
    }

    /**
     * 从未选过的顶点中选出最小顶点
     * @param map 顶点与终点距离
     * @param select 已经选择过的顶点
     */
    public Node<Integer> miniumDistanceNode(Map<Node<Integer>, Integer> map, Set<Node<Integer>> select) {
        int min = Integer.MAX_VALUE;
        Node<Integer> res = null;
        for (Node<Integer> cur: map.keySet()) {
            if (!select.contains(cur) && map.get(cur) < min) {
                min = map.get(cur);
                res = cur;
            }
        }
        return res;
    }

    class DijkstralUpdate {
        class NodeInfo<T>{
            public Node<T> node;
            public int distance;
            public NodeInfo(Node<T> node, int distance) {
                this.node = node;
                this.distance = distance;
            }
        }
        //通过堆结构使得存取节点的复杂度降到O(logn)
        class NodeMinHeap<T> {
            //实际堆结构
            public Node<T>[] nodes;
            //存储节点对应的下标：①若为普通节点，就是实际的nodes[]下标；②若是已经被访问的，设为-1
            public Map<Node<T>, Integer> idxMap;
            //存储当前节点的最短距离
            public Map<Node<T>, Integer> dstMap;
            //当前实际存在的节点数，用于实现插入
            int size;

            public NodeMinHeap(int size) {
                nodes = new Node[size];
                idxMap = new HashMap<>();
                dstMap = new HashMap<>();
                size = 0;
            }

            public void insertOrUpdateOrIgnore(Node<T> node, int distance) {
                if (!hasEntered(node)) {
                    //节点是fresh，因此应该插入新节点
                    nodes[size] = node;//最末尾位置插入
                    idxMap.put(node, size);
                    dstMap.put(node, distance);
                    insertHepify(node, size++);//调整堆
                } else if (!hasUsed(node)) {
                    //还未使用的节点，有可能需要更新
                    if (dstMap.get(node) > distance) {
                        //新的距离更小，进行更新
                        dstMap.put(node, distance);
                        //此时node的距离被修改，他在堆中的位置应该被修改，当做被新插入的节点处理
                        insertHepify(node, idxMap.get(node));
                        //idxMap会在swap()中自动更新，无需修改。
                    }
                }
            }

            //得到堆顶元素，并标记为已经使用，调整堆结构
            public NodeInfo<T> pop() {
                NodeInfo<T> res = new NodeInfo<>(nodes[0], dstMap.get(nodes[0]));
                swap(0, size - 1);
                heapify(0);
                idxMap.put(nodes[size - 1], -1);//标记为已经访问
                dstMap.remove(nodes[size - 1]);
                nodes[--size] = null;
                return res;
            }

            public boolean isEmpty() {
                return size == 0;
            }
            
            public boolean hasEntered(Node<T> node) {
                return idxMap.containsKey(node);
            }

            //节点是否被使用过，即使用它进行最短路径更新
            public boolean hasUsed(Node<T> node) {
                return idxMap.containsKey(node) && idxMap.get(node) == -1;
            }

            //插入一个节点用于调整堆的方法，具体的节点插入在调用他的方法处
            /* 
                节点会在nodes[]的末尾插入【即当前size处】，并且会根据到node的距离进行更新
            */
            public void insertHepify(Node<T> node, int idx) {
                int p;
                //父节点的下标为(cur - 1) / 2
                //小顶堆，因此距离越小越上
                while (dstMap.get(nodes[p = (idx - 1) / 2]) > dstMap.get(nodes[idx])) {
                    swap(idx, p);
                    idx = p; //继续向上调整
                }
            }

            //顶层节点被换走后，需要通过自上而下调整满足堆结构，时间复杂度O(logn)
            public void heapify(int start) {
                int left, right, min, idx = start;
                while (idx < size) {
                    min = idx;
                    left = idx * 2 + 1;
                    right = idx * 2 + 2;
                    if (left < size) {
                        if (dstMap.get(nodes[left]) < dstMap.get(nodes[min])) min = left;
                    }
                    if (right < size) {
                         if (dstMap.get(nodes[right]) < dstMap.get(nodes[min])) min = right;
                    }
                    if (min != idx) {
                        swap(min, idx);
                        idx = min;
                    } else break;
                }
            }

            //交换两个节点的在的位置，不进要nodes，还需要idxMap
            public void swap(int i, int j) {
                idxMap.put(nodes[i], j);
                idxMap.put(nodes[j], i);
                Node<T> temp = nodes[i];
                nodes[i] = nodes[j];
                nodes[j] = temp;
            }
        }

        public  Map<Node<Integer>, Integer> dijkstral(Node<Integer> node) {
            NodeMinHeap<Integer> minHeap = new NodeMinHeap<>(100);
            Map<Node<Integer>, Integer> res = new HashMap<>();
            minHeap.insertOrUpdateOrIgnore(node, 0);//起点-> 起点 0
            NodeInfo<Integer> cur;
            int distance;
            while (!minHeap.isEmpty()) {
                cur = minHeap.pop();
                distance = cur.distance;
                for (Edge<Integer> e: cur.node.edges) {
                    if (!res.containsKey(cur.node) || (distance = distance + e.weight) < res.get(cur.node)) {
                        res.put(cur.node, distance);
                        minHeap.insertOrUpdateOrIgnore(e.out, distance);
                    }
                }
            }
            return res;
        }
    }
 }
